package com.my.leetcode;

import org.apache.commons.collections4.MapUtils;
import org.apache.kafka.common.metrics.stats.Max;

import java.util.*;
import java.util.regex.Pattern;

public class TreeProblems {


    public static void main(String[] args) {

        TreeProblems problems = new TreeProblems();
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        node2.left = node1;
        node2.right = node3;
        node4.left = node2;
        node4.right = node5;

        a = new ArrayList<>();
        problems.middleFirst(node4);
        System.out.println(a);
        System.out.println(problems.treeToDoublyList(node4));

    }

    /**
     * @author zlx
     * @Description 剑指 Offer 36. 二叉搜索树与双向链表
     * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
     *
     *
     *
     * 为了让您更好地理解问题，以下面的二叉搜索树为例：
     *
     *
     *
     *
     *
     *
     *
     * 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
     *
     * 下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
     *
     *
     *
     *
     *
     *
     *
     * 特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
     * @Date 3/22/21
     * @Param [root]
     * @return com.my.leetcode.TreeProblems.Node
     **/
    public Node treeToDoublyList(Node root) {

        dfsTreeToDoublyList(root);
        pre.right = head;
        head.left = pre;
        return head;
    }

    Node pre, head;
    public void dfsTreeToDoublyList(Node node){

        if(node == null){
            return ;
        }
        dfsTreeToDoublyList(node.left);
        if(pre == null){
            head = node;
        }else{
            pre.right = node;
        }
        node.left = pre;
        pre = node;
        dfsTreeToDoublyList(node.right);
    }


    public static List<Integer> a = new ArrayList<>();

    /**
     * @author zlx
     * @Description 中序遍历
     * @Date 3/22/21
     * @Param [node]
     * @return void
     **/
    public void middleFirst(Node node){

        if(node == null){
            return ;
        }
        middleFirst(node.left);
        a.add(node.val);
        middleFirst(node.right);

    }




    int res = Integer.MIN_VALUE;
    /**
     * @author zlx
     * @Description 124. 二叉树中的最大路径和 hard
     * 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
     *
     * 路径和 是路径中各节点值的总和。
     *
     * 给你一个二叉树的根节点 root ，返回其 最大路径和 。
     *
     *
     *
     * 示例 1：
     *
     *
     * 输入：root = [1,2,3]
     * 输出：6
     * 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
     * 示例 2：
     *
     *
     * 输入：root = [-10,9,20,null,null,15,7]
     * 输出：42
     * 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
     *
     *
     * 提示：
     *
     * 树中节点数目范围是 [1, 3 * 104]
     * -1000 <= Node.val <= 1000
     * @Date 3/22/21
     * @Param [root]
     * @return int
     **/
    public int maxPathSum(TreeNode root) {
        maxdfsPathSum(root);
        return res;
    }

    public int maxdfsPathSum(TreeNode node){
        if(node == null){
            return 0;
        }
        int val = node.val;
        int maxLeft = Math.max(maxdfsPathSum(node.left), 0);
        int maxRight = Math.max(maxdfsPathSum(node.right), 0);
        res = Math.max(res, val + maxLeft + maxRight);
        return Math.max(maxLeft, maxRight) + val;
    }


    /**
     * @author zlx
     * @Description 1584. 连接所有点的最小费用 middle
     * 给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。
     *
     * 连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。
     *
     * 请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
     *
     *
     *
     * 示例 1：
     *
     *
     *
     * 输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
     * 输出：20
     * 解释：
     *
     * 我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
     * 注意到任意两个点之间只有唯一一条路径互相到达。
     * 示例 2：
     *
     * 输入：points = [[3,12],[-2,5],[-4,1]]
     * 输出：18
     * 示例 3：
     *
     * 输入：points = [[0,0],[1,1],[1,0],[-1,1]]
     * 输出：4
     * 示例 4：
     *
     * 输入：points = [[-1000000,-1000000],[1000000,1000000]]
     * 输出：4000000
     * 示例 5：
     *
     * 输入：points = [[0,0]]
     * 输出：0
     *
     *
     * 提示：
     *
     * 1 <= points.length <= 1000
     * -106 <= xi, yi <= 106
     * 所有点 (xi, yi) 两两不同。
     *
     * 解题思路： 根本是构建最小生成树，
     * 官方解答是使用 Kruskal算法
     * （1）假设图Graph 有n个节点，e条边；构建一个新图GrapNew
     *
     * （2）将节点之间的边按从小到达进行排序；
     *
     * （3）循环：从权值最小的边开始遍历每条边 直至图Graph中所有的节点都在同一个连通分量中
     *
     *            if 这条边连接的两个节点于图Graphnew中不在同一个连通分量中 添加这条边到图Graphnew中；
     *            if 这条边连接的两个节点于图Graphnew中在同一个连通分量中 则不添加；
     *            （同一个联通分量： 能否构成闭环）
     * @Date 1/21/21
     * @Param [points]
     * @return int
     **/
    public int minCostConnectPoints(int[][] points) {

        int n = points.length;
        if(n == 1){
            return 0;
        }

        int res = 0;

        List<Edge> edges = new ArrayList<>();
        for(int i = 0;i < n;i++){
            for(int j = i + 1;j < n;j++){
                edges.add(new Edge(distanceOfPoints(i, j, points),i, j));
            }
        }

        Collections.sort(edges, new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.len - o2.len;
            }
        });

        KruskalUnionSet kruskalUnionSet = new KruskalUnionSet(n);

        int nodeNums = 1;
        for(Edge edge : edges){
            if(kruskalUnionSet.unionSet(edge.start, edge.end)){
                res += edge.len;
                nodeNums ++;
                if(nodeNums == n){
                    break;
                }
            }
        }

        return res;
    }


    /**
     * @author zlx
     * @Description 基于并查集概念判断是否联通
     * @Date 1/21/21
     * @Param
     * @return
     **/
    public class KruskalUnionSet{

        int [] f;
        int [] rank;
        int n;

        public KruskalUnionSet(int n) {
            this.n = n;
            this.f = new int[n];
            this.rank = new int[n];
            for(int i = 0;i < n;i++){
                rank[i] = 1;
                f[i] = i;
            }
        }

        public int find(int x){

            if(x != f[x]){
                return find(f[x]);
            }
            return f[x];
        }

        public boolean unionSet(int x, int y){

            int rootX = find(x);
            int rootY = find(y);

            if(rootX == rootY){
                return false;
            }

            if(rank[rootX] == rank[rootY]){
                f[rootX] = rootY;
                rank[rootY] ++;

            }else if(rank[rootX] < rank[rootY]){
                f[rootX] = rootY;
            }else{
                f[rootY] = rootX;
            }
            return true;
        }




    }

    public int distanceOfPoints(int x, int y, int[][] points){
        return Math.abs(points[x][0] - points[y][0]) + Math.abs(points[x][1] - points[y][1]);
    }

    public class Edge{

        private int len;

        private int start;

        private int end;

        public int getLen() {
            return len;
        }

        public void setLen(int len) {
            this.len = len;
        }

        public int getStart() {
            return start;
        }

        public void setStart(int start) {
            this.start = start;
        }

        public int getEnd() {
            return end;
        }

        public void setEnd(int end) {
            this.end = end;
        }

        public Edge(int len, int start, int end) {
            this.len = len;
            this.start = start;
            this.end = end;
        }
    }

    /**
     * @author zlx
     * @Description 865. 具有所有最深节点的最小子树 middle
     * 给定一个根为 root 的二叉树，每个节点的深度是 该节点到根的最短距离 。
     *
     * 如果一个节点在 整个树 的任意节点之间具有最大的深度，则该节点是 最深的 。
     *
     * 一个节点的 子树 是该节点加上它的所有后代的集合。
     *
     * 返回能满足 以该节点为根的子树中包含所有最深的节点 这一条件的具有最大深度的节点。
     *
     *
     *
     * 注意：本题与力扣 1123 重复：https://leetcode-cn.com/problems/lowest-common-ancestor-of-deepest-leaves/
     *
     *
     *
     * 示例 1：
     *
     *
     *
     * 输入：root = [3,5,1,6,2,0,8,null,null,7,4]
     * 输出：[2,7,4]
     * 解释：
     * 我们返回值为 2 的节点，在图中用黄色标记。
     * 在图中用蓝色标记的是树的最深的节点。
     * 注意，节点 5、3 和 2 包含树中最深的节点，但节点 2 的子树最小，因此我们返回它。
     * 示例 2：
     *
     * 输入：root = [1]
     * 输出：[1]
     * 解释：根节点是树中最深的节点。
     * 示例 3：
     *
     * 输入：root = [0,1,3,null,2]
     * 输出：[2]
     * 解释：树中最深的节点为 2 ，有效子树为节点 2、1 和 0 的子树，但节点 2 的子树最小。
     *
     *
     * 提示：
     *
     * 树中节点的数量介于 1 和 500 之间。
     * 0 <= Node.val <= 500
     * 每个节点的值都是独一无二的。
     *
     * 解题思路： 求最深节点的最小字树，当节点的左子树深度=右子树深度，最小树是该节点；
     *                              当节点的左子树深度<右子树深度，最小树在该节点的右子树中；
     *                              当节点的左子树深度>右子树深度，最小树是该节点的左子树中
     * @Date 2020-12-22
     * @Param [root]
     * @return com.my.leetcode.TreeNode
     **/

    public TreeNode lcaDeepestLeaves(TreeNode root) {

        int left = dfsGetHeight(root.left);
        int right = dfsGetHeight(root.right);
        if(left == right){
            return root;
        }else if(left < right){
            return lcaDeepestLeaves(root.right);
        }else{
            return lcaDeepestLeaves(root.left);
        }
    }


    //求树的最大深度
    public int dfsGetHeight(TreeNode node){
        if(node == null){
            return 0;
        }
        return Math.max(dfsGetHeight(node.left), dfsGetHeight(node.right)) + 1;
    }



    public int countNodes(TreeNode root) {

        if(root == null){
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        int count = 0;
        queue.add(root);
        while (!queue.isEmpty()){

            int levelSize = queue.size();
            for(int i = 0;i < levelSize;i++) {
                TreeNode node = queue.poll();
                if(node.left != null){
                    queue.add(node.left);
                }
                if(node.right != null){
                    queue.add(node.right);
                }
            }
            count += levelSize;
        }
        return count;
    }


    /**
     * @author zlx
     * @Description 1161. 最大层内元素和
     * 给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。
     *
     * 请你找出层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。
     *
     *
     *
     * 示例 1：
     *
     *
     *
     * 输入：root = [1,7,0,7,-8,null,null]
     * 输出：2
     * 解释：
     * 第 1 层各元素之和为 1，
     * 第 2 层各元素之和为 7 + 0 = 7，
     * 第 3 层各元素之和为 7 + -8 = -1，
     * 所以我们返回第 2 层的层号，它的层内元素之和最大。
     * 示例 2：
     *
     * 输入：root = [989,null,10250,98693,-89388,null,null,null,-32127]
     * 输出：2
     *
     *
     * 提示：
     *
     * 树中的节点数介于 1 和 10^4 之间
     * -10^5 <= node.val <= 10^5
     *
     * BFS按层遍历
     * @Date 2020-12-21
     * @Param [root]
     * @return int
     **/
    public int maxLevelSum(TreeNode root) {

        if(root == null){
            return 0;
        }

        if(root.left == null && root.right == null){
            return 1;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        int max = Integer.MIN_VALUE;
        int maxLevel = 0 ;
        queue.add(root);

        int level = 0;
        while (!queue.isEmpty()){

            level ++;
            int levelSize = queue.size();
            int levelSum = 0;
            for(int i = 0;i < levelSize;i++){
                TreeNode tmp = queue.poll();
                levelSum += tmp.val;
                if(tmp.left != null){
                    queue.add(tmp.left);
                }
                if(tmp.right != null){
                    queue.add(tmp.right);
                }
            }

            if(levelSum > max){
                max = levelSum;
                maxLevel = level;
            }
        }
        return maxLevel;
    }


    /**
     * @author zlx
     * @Description 530. 二叉搜索树的最小绝对差  easy
     * 给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
     *
     *
     *
     * 示例：
     *
     * 输入：
     *
     *    1
     *     \
     *      3
     *     /
     *    2
     *
     * 输出：
     * 1
     *
     * 解释：
     * 最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
     * @Date 2020-10-12
     * @Param [root]
     * @return int
     **/
    public int getMinimumDifference(TreeNode root) {

        minDifference = Integer.MAX_VALUE;
        prevVal = Integer.MIN_VALUE / 2;
        inOrderDfs(root);
        return minDifference;
    }


    public int minDifference = Integer.MAX_VALUE;
    public int prevVal = Integer.MIN_VALUE / 2;

    public void inOrderDfs(TreeNode node){

        if(node == null){
            return ;
        }

        inOrderDfs(node.left);
        minDifference = Math.min(minDifference, (node.val - prevVal));
        prevVal = node.val;
        inOrderDfs(node.right);
    }


    /**
     * @author zlx
     * @Description 701. 二叉搜索树中的插入操作  middle
     * 给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。
     *
     * 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
     *
     *
     *
     * 例如, 
     *
     * 给定二叉搜索树:
     *
     *         4
     *        / \
     *       2   7
     *      / \
     *     1   3
     *
     * 和 插入的值: 5
     * 你可以返回这个二叉搜索树:
     *
     *          4
     *        /   \
     *       2     7
     *      / \   /
     *     1   3 5
     * 或者这个树也是有效的:
     *
     *          5
     *        /   \
     *       2     7
     *      / \   
     *     1   3
     *          \
     *           4
     *
     *
     * 提示：
     *
     * 给定的树上的节点数介于 0 和 10^4 之间
     * 每个节点都有一个唯一整数值，取值范围从 0 到 10^8
     * -10^8 <= val <= 10^8
     * 新值和原始二叉搜索树中的任意节点值都不同
     *
     * 解题思路： 根据dfs遍历方式求解，当val值大于当前节点，val肯定是BST的右子树；val值<当前节点值，val肯定是BST的左子树
     * @Date 2020-09-30
     * @Param [root, val]
     * @return com.my.leetcode.TreeNode
     **/
    public TreeNode insertIntoBST(TreeNode root, int val) {

        return dfsInsertIntoBST(root, val);
    }


    public TreeNode dfsInsertIntoBST(TreeNode node, int val){

        if(node == null){
            return new TreeNode(val);
        }

        TreeNode tmpNode = node;

        if(val < node.val){
            node.left = dfsInsertIntoBST(node.left, val);
        }else{

            node.right = dfsInsertIntoBST(node.right, val);
        }
        return tmpNode;
    }


    static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }

        @Override
        public String toString() {
            return super.toString();
        }
    }




    /**
     * @author zlx
     * @Description 117. 填充每个节点的下一个右侧节点指针 II middle
     * 给定一个二叉树
     *
     * struct Node {
     *   int val;
     *   Node *left;
     *   Node *right;
     *   Node *next;
     * }
     * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
     *
     * 初始状态下，所有 next 指针都被设置为 NULL。
     *
     *
     *
     * 进阶：
     *
     * 你只能使用常量级额外空间。
     * 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
     *
     *
     * 示例：
     *
     *
     *
     * 输入：root = [1,2,3,4,5,null,7]
     * 输出：[1,#,2,3,#,4,5,7,#]
     * 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
     * @Date 2020-09-28
     * @Param [root]
     * @return com.my.leetcode.TreeProblems.Node
     **/
    public Node connect(Node root) {

        if(root == null){
            return root;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){

            int count = queue.size();
            for(int i = 0;i < count;i++){

                Node tmp = queue.poll();
                if(i != count - 1){
                    tmp.next = queue.peek();
                }else{
                    tmp.next = null;
                }
                if(tmp.left != null){
                    queue.add(tmp.left);
                }

                if(tmp.right != null){
                    queue.add(tmp.right);
                }
            }
        }

        return root;

    }


    /**
     * @author zlx
     * @Description //TODO
     * @Date 4/11/21
     * @Param [root, p, q]
     * @return com.my.leetcode.TreeNode
     **/
    public TreeNode lowestCommonAncestorI(TreeNode root, TreeNode p, TreeNode q) {

        boolean res = dfs(root,p, q);
        System.out.println(ans);
        return ans;
    }

    TreeNode ans = null;
    public boolean dfs(TreeNode root, TreeNode p, TreeNode q){

        if(root == null){
            return false;
        }

        boolean lson = dfs(root.left, p, q);
        boolean rson = dfs(root.right, p, q);

        if((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))){
            ans = root;
        }
        return lson || rson || (root.val == p.val) || (root.val == q.val);
    }



    /**
     * @author zlx
     * @Description 排序二叉树求最近节点
     * @Date 2020-09-27
     * @Param [root, p, q]
     * @return com.my.leetcode.TreeNode
     **/
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        TreeNode res = root;
        while (true){

            if(res.val < p.val && res.val < q.val){
                res = res.right;
            }else if(res.val > p.val && res.val > q.val){
                res = res.left;
            }else{
                break;
            }
        }
        return res;
    }



    public Map<Integer, Integer> inorderMap = new HashMap<>();


    /**
     * @author zlx
     * @Description 106. 从中序与后序遍历序列构造二叉树  middle
     * 根据一棵树的中序遍历与后序遍历构造二叉树。
     *
     * 注意:
     * 你可以假设树中没有重复的元素。
     *
     * 例如，给出
     *
     * 中序遍历 inorder = [9,3,15,20,7]
     * 后序遍历 postorder = [9,15,7,20,3]
     * 返回如下的二叉树：
     *
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * @Date 2020-09-25
     * @Param [inorder, postorder]
     * @return com.my.leetcode.TreeNode
     **/
    public TreeNode buildTreeII(int[] inorder, int[] postorder) {

        for(int i = 0;i < inorder.length;i++){
            inorderMap.put(inorder[i], i);
        }
        return dfsIPBuildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }


    public TreeNode dfsIPBuildTree(int [] inorder, int inStart, int inEnd, int [] postorder, int postStart, int postEnd){


        System.out.println("inStart:" + inStart + "   inEnd :" + inEnd);
        System.out.println("postStart:" + postStart + "   postEnd :" + postEnd);

        if(inStart > inEnd || postStart > postEnd){
            return null;
        }
        TreeNode node = new TreeNode(postorder[postEnd]);
        int middle = inorderMap.get(node.val);
//        for(int i = inStart;i <=inEnd;i++){
//            if(inorder[i] == postorder[postEnd]){
//                middle = i;
//                break;
//            }
//        }
        System.out.println("======middle is:====" + middle);
        System.out.println();
        node.left = dfsIPBuildTree(inorder, inStart, middle - 1, postorder, postStart, postStart + middle - inStart - 1);

        node.right = dfsIPBuildTree(inorder, middle + 1, inEnd, postorder, postStart + middle - inStart, postEnd - 1);

        return node;
    }



    public int[] findMode(TreeNode root) {

        List<Integer> res = new ArrayList<>();
        treeValMap = new HashMap<>();
        dfsBST(root);
        if(treeValMap.size() == 0){

            return new int[0];
        }

        treeValMap.forEach((k, v) ->{
            if(v == maxVal){
                res.add(k);
            }
        });
        int [] resArray = new int[res.size()];
        for(int i = 0;i < resArray.length;i++){
            resArray[i] = res.get(i);
        }
        return resArray;
    }

    Map<Integer, Integer> treeValMap = new HashMap<>();
    Integer maxVal = Integer.MIN_VALUE;
    public void dfsBST(TreeNode node){

        if(node == null){
            return ;
        }

        dfsBST(node.left);
        if(!treeValMap.containsKey(node.val)){
            treeValMap.put(node.val, 1);
        }else {
            treeValMap.put(node.val, treeValMap.get(node.val) + 1);
        }
        maxVal = maxVal > treeValMap.get(node.val) ? maxVal : treeValMap.get(node.val);
        dfsBST(node.right);
    }


    /**
     * @author zlx
     * @Description 617. 合并二叉树 easy
     * 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
     *
     * 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
     *
     * 示例 1:
     *
     * 输入:
     * 	Tree 1                     Tree 2
     *           1                         2
     *          / \                       / \
     *         3   2                     1   3
     *        /                           \   \
     *       5                             4   7
     * 输出:
     * 合并后的树:
     * 	     3
     * 	    / \
     * 	   4   5
     * 	  / \   \
     * 	 5   4   7
     *
     *
     * 解题思路：基于dfs进行求解
     *
     * @Date 2020-09-23
     * @Param [t1, t2]
     * @return com.my.leetcode.TreeNode
     **/
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {

        if(t1 == null && t2 == null){
            return new TreeNode(0);
        }

        if(t1 == null){
            return t2;
        }

        if(t2 == null){
            return t1;
        }

        TreeNode node = new TreeNode(t1.val + t2.val);

        node.left = mergeTrees(t1.left, t2.left);

        node.right = mergeTrees(t1.right, t2.right);

        return node;

    }




    /**
     * @author zlx
     * @Description //968. 监控二叉树  hard
     * 给定一个二叉树，我们在树的节点上安装摄像头。
     *
     * 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
     *
     * 计算监控树的所有节点所需的最小摄像头数量。
     *
     *
     *
     * 示例 1：
     *
     *
     *
     * 输入：[0,0,null,0,0]
     * 输出：1
     * 解释：如图所示，一台摄像头足以监控所有节点。
     * 示例 2：
     *
     *
     *
     * 输入：[0,0,null,0,null,0,null,null,0]
     * 输出：2
     * 解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
     *
     * 提示：
     *
     * 给定树的节点数的范围是 [1, 1000]。
     * 每个节点的值都是 0。
     *
     * 解题思路： 对任意一个节点root， 有3中状态
     * a： root节点必须放置监控，覆盖整课树需要的监控节点数
     * b： 无论root节点是否放置监控，覆盖整课树需要的监控节点数
     * c: 覆盖2棵子树需要的监控节点数量
     *
     * root节点的左右节点，分别也有3个状态，la,lb,lc  ra,rb,rc
     *
     * 因此：
     * a = lc + rc + 1;
     * b = min(a, min(la + rb, ra + lb))
     * c = min(a, lb+lc)
     *
     * 然后基于dfs进行求解
     * @Date 2020-09-22
     * @Param [root]
     * @return int
     **/
    public int minCameraCover(TreeNode root) {

        int [] array = dfsMinCameraCover(root);
        return array[1];
    }

    public int [] dfsMinCameraCover(TreeNode node){

        if(node == null){
            return new int [] {Integer.MAX_VALUE/2, 0, 0};
        }

        int [] leftArray = dfsMinCameraCover(node.left);

        int [] rightArray = dfsMinCameraCover(node.right);

        int [] array = new int[3];

        array[0] = leftArray[2] + rightArray[2] +1;
        array[1] = Math.min(array[0], Math.min(leftArray[0] + rightArray[1], leftArray[1] + rightArray[0]));
        array[2] = Math.min(array[0], leftArray[1] + rightArray[1]);
        return array;
    }


    /**
     * @author zlx
     * @Description 538. 把二叉搜索树转换为累加树
     * 给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
     *
     *
     *
     * 例如：
     *
     * 输入: 原始二叉搜索树:
     *               5
     *             /   \
     *            2     13
     *
     * 输出: 转换为累加树:
     *              18
     *             /   \
     *           20     13
     *
     *  解题思路：二叉搜索树是一棵空树，或者是具有下列性质的二叉树：
     *
     * 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
     *
     * 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
     *
     * 它的左、右子树也分别为二叉搜索树。
     *
     * 由这样的性质我们可以发现，二叉搜索树的中序遍历是一个单调递增的有序序列。如果我们反序地中序遍历该二叉搜索树，即可得到一个单调递减的有序序列。
     *
     * 方法一：反序中序遍历
     *
     * @Param [root]
     * @return com.my.leetcode.TreeNode
     **/
    public TreeNode convertBST(TreeNode root) {
        if(root != null){
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }


    public TreeNode dfsConvertBST(TreeNode node){

        if(node == null){
            return null;
        }
        TreeNode node1 = new TreeNode(node.val);
        TreeNode rightNode = dfsConvertBST(node.right);
        if(rightNode != null){
            node1.val += rightNode.val;
        }
        node1.right = rightNode;

        TreeNode leftNode = dfsConvertBST(node.left);
        if(leftNode != null){
            leftNode.val += node1.val;
        }
        node1.left = leftNode;
        return node1;
    }

    /**
     * @author zlx
     * @Description 404. 左叶子之和  easy
     * 计算给定二叉树的所有左叶子之和。
     *
     * 示例：
     *
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     *
     * 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
     * @Date 2020-09-19
     * @Param [root]
     * @return int
     **/
    public int sumOfLeftLeaves(TreeNode root) {

        sumOfLeaves = 0;
        dfsSumOfLeftLeaves(root);

        return sumOfLeaves;
    }

    public int sumOfLeaves = 0;

    public void dfsSumOfLeftLeaves(TreeNode node){

        if(node == null){
            return ;
        }

        if(node.left != null && node.left.left == null && node.left.right == null){
            sumOfLeaves += node.left.val;
        }

        dfsSumOfLeftLeaves(node.left);
        dfsSumOfLeftLeaves(node.right);
    }



    /**
     * @author zlx
     * @Description 226. 翻转二叉树 easy
     * 翻转一棵二叉树。
     *
     * 示例：
     *
     * 输入：
     *
     *      4
     *    /   \
     *   2     7
     *  / \   / \
     * 1   3 6   9
     * 输出：
     *
     *      4
     *    /   \
     *   7     2
     *  / \   / \
     * 9   6 3   1
     * @Date 2020-09-16
     * @Param [root]
     * @return com.my.leetcode.TreeNode
     **/
    public TreeNode invertTree(TreeNode root) {

        if(root == null || (root.left == null && root.right == null)){
            return root;
        }
        return dfsInverseTree(root);
    }


    public TreeNode dfsInverseTree(TreeNode node){

        if(node == null){
            return null;
        }

        if(node.left == null && node.right == null){
            return new TreeNode(node.val);
        }

        TreeNode leftNode = node.left;
        TreeNode rightNode = node.right;

        node.left = dfsInverseTree(rightNode);
        node.right = dfsInverseTree(leftNode);

        return node;

    }

    public List<Double> averageOfLevels(TreeNode root) {
        if(root == null){
            return null;
        }
        List<Double> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int count = queue.size();
            double sum = 0.0;
            for(int i =0;i < count;i++){
                TreeNode tmpNode = queue.poll();
                sum += root.val;
                if(tmpNode.left != null){
                    queue.add(tmpNode.left);
                }

                if(tmpNode.right != null){
                    queue.add(tmpNode.right);
                }
            }
            Double tmp = sum * 1.0 / count;
            res.add(tmp);
        }
        return res;
    }

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root ==  null){
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> rows = new ArrayList<>();
            for(int i = 0;i < size;i++){
                TreeNode tmp = queue.poll();
                rows.add(tmp.val);
                if(tmp.left != null){
                    queue.offer(tmp.left);
                }
                if(tmp.right != null){
                    queue.offer(tmp.right);
                }
            }
            res.add(rows);
        }
        List<List<Integer>> realRes = new ArrayList<>();
        for(int i = res.size()-1;i >= 0;i--){
            realRes.add(res.get(i));
        }
        return realRes;
    }

    /**
     * @author zlx
     * @Description  109. 有序链表转换二叉搜索树 middle
     * 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
     *
     * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
     *
     * 示例:
     *
     * 给定的有序链表： [-10, -3, 0, 5, 9],
     *
     * 一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
     *
     *       0
     *      / \
     *    -3   9
     *    /   /
     *  -10  5
     *
     *  解题思路： dfs方法，找到中间点，分别构建左右子树
     * @Date 2020-08-18
     * @Param [head]
     * @return com.my.leetcode.TreeNode
     **/
    public TreeNode sortedListToBST(ListNode head) {
        return dfsToBST(head, null);

    }


    public TreeNode dfsToBST(ListNode headIn, ListNode tailIn){

        if(headIn == null || headIn == tailIn){
            return null;
        }
        ListNode head = headIn;
        ListNode tail = tailIn;

        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next!= null && fast != tail && fast.next != tail){
            slow = slow.next;
            fast = fast.next.next;
        }

        TreeNode treeNode = new TreeNode(slow.val);
        treeNode.left = dfsToBST(headIn, slow);
        treeNode.right = dfsToBST(slow.next, tailIn);

        return treeNode;
    }
    

    /**
     * @author zlx
     * @Description 110. 平衡二叉树 easy
     * 给定一个二叉树，判断它是否是高度平衡的二叉树。
     *
     * 本题中，一棵高度平衡二叉树定义为：
     *
     * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
     *
     * 示例 1:
     *
     * 给定二叉树 [3,9,20,null,null,15,7]
     *
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回 true 。
     *
     * 示例 2:
     *
     * 给定二叉树 [1,2,2,3,3,null,null,4,4]
     *
     *        1
     *       / \
     *      2   2
     *     / \
     *    3   3
     *   / \
     *  4   4
     * 返回 false 。
     *
     *
     * 解法一： 使用自顶向下解法
     * @Date 2020-08-17
     * @Param [root]
     * @return boolean
     **/
    public boolean isBalanced(TreeNode root) {

        if(root == null){
            return true;
        }else{

            return Math.abs(heightOfTree(root.left)- heightOfTree(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }

    }


    public int heightOfTree(TreeNode treeNode){

        if(treeNode == null){
            return 0;
        }
        return Math.max(heightOfTree(treeNode.left), heightOfTree(treeNode.right)) + 1;
    }





    /**
     * @author zlx
     * @Description
     * @Date 2020-08-12
     * @Param [root]
     * @return com.my.leetcode.TreeNode
     **/
    public TreeNode increasingBST(TreeNode root) {

        nodeVals = new ArrayList<>();
        middleFirstTree(root);

        TreeNode res = new TreeNode(nodeVals.get(0));
        TreeNode tmp = res;
        for(int i = 1;i < nodeVals.size();i++){

            tmp.left = null;
            tmp.right = new TreeNode(nodeVals.get(i));
            tmp = tmp.right;
        }
        return res;
    }

    public static List<Integer> nodeVals = new ArrayList<>();
    //中序遍历 左根右
    public void middleFirstTree(TreeNode node){

        if(node == null){
            return ;
        }
        middleFirstTree(node.left);
        nodeVals.add(node.val);
        middleFirstTree(node.right);
    }

    /**
     * @author zlx
     * @Description 95. 不同的二叉搜索树 II
     * 给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。
     *
     *
     *
     * 示例：
     *
     * 输入：3
     * 输出：
     * [
     *   [1,null,3,2],
     *   [3,2,null,1],
     *   [3,1,null,null,2],
     *   [2,1,3],
     *   [1,null,2,null,3]
     * ]
     * 解释：
     * 以上的输出对应以下 5 种不同结构的二叉搜索树：
     *
     *    1         3     3      2      1
     *     \       /     /      / \      \
     *      3     2     1      1   3      2
     *     /     /       \                 \
     *    2     1         2                 3
     *
     *
     * 提示：
     *
     * 0 <= n <= 8
     * @Date 2020-07-21
     * @Param [n]
     * @return java.util.List<com.my.leetcode.TreeNode>
     **/
    public List<TreeNode> generateTrees(int n) {

        if(n == 0){
            return new ArrayList();
        }
        return generateTrees(1, n);
    }


    public List<TreeNode> generateTrees(int start, int end){

        List<TreeNode> res = new ArrayList<>();
        if(start > end){
            res.add(null);
            return res;
        }

        if(start == end){
            res.add(new TreeNode(start));
            return res;
        }

        List<TreeNode> left, right;
        for(int i = start;i<=end;i++){

            left = generateTrees(start, i-1);
            right = generateTrees(i + 1, end);

            for(TreeNode leftNode : left){
                for(TreeNode rightNode : right){
                    TreeNode root = new TreeNode(i);
                    root.left = leftNode;
                    root.right = rightNode;
                    res.add(root);
                }
            }
        }
        return res;
    }

    /**
     * @author zlx
     * @Description 108. 将有序数组转换为二叉搜索树
     * 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
     *
     * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
     *
     * 示例:
     *
     * 给定有序数组: [-10,-3,0,5,9],
     *
     * 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
     *
     *       0
     *      / \
     *    -3   9
     *    /   /
     *  -10  5
     *
     *  解题思路：平衡二叉搜索树的中序遍历是有序数组，根据数组构建平衡二叉树是不唯一的，最简单的方式是每次一数组中间值为根节点，左边的是左子树，右边是右子树，高度差不会超过1
     *  基于dfs构建二叉搜索树
     *
     * @Date 2020-07-06
     * @Param [nums]
     * @return com.my.leetcode.TreeNode
     **/
    public TreeNode sortedArrayToBST(int[] nums) {

        if(nums == null || nums.length <= 0){
            return null;
        }

        return buildBTByDFS(nums, 0, nums.length - 1);
    }

    public TreeNode buildBTByDFS(int [] nums, int start, int end){

        if(start > end){
            return null;
        }

        int middle = (start + end) / 2;
        TreeNode node  = new TreeNode(nums[middle]);
        node.left = buildBTByDFS(nums, start, middle - 1);
        node.right = buildBTByDFS(nums, middle + 1, end);
        return node;
    }


    /**
     * 1028. 从先序遍历还原二叉树 hard
     * 我们从二叉树的根节点 root 开始进行深度优先搜索。
     *
     * 在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。
     *
     * 如果节点只有一个子节点，那么保证该子节点为左子节点。
     *
     * 给出遍历输出 S，还原树并返回其根节点 root。
     *
     *
     *
     * 示例 1：
     *
     *
     *
     * 输入："1-2--3--4-5--6--7"
     * 输出：[1,2,5,3,4,6,7]
     * 示例 2：
     *
     *
     *
     * 输入："1-2--3---4-5--6---7"
     * 输出：[1,2,5,3,null,6,null,4,null,7]
     * 示例 3：
     *
     *
     *
     * 输入："1-401--349---90--88"
     * 输出：[1,401,null,349,88,90]
     *
     *
     * 提示：
     *
     * 原始树中的节点数介于 1 和 1000 之间。
     * 每个节点的值介于 1 和 10 ^ 9 之间。
     * @param S
     * @return
     */
    public TreeNode recoverFromPreorder(String S) {

        if(S == null || S.length() <= 0){
            return null;
        }

        if(S.length() == 1){
            return new TreeNode(Integer.parseInt(S));
        }
       return  buildTree(S, 0, S.length()-1, 1);
    }


    public TreeNode buildTree(String s, int index, int lastIndex, int times){

        //System.out.println("times is:====" + times + " index is:----" + index + "   lastIndex is:----" + lastIndex);
        if(index > lastIndex){
            return null;
        }
        String a = "";
        for(int i = 0;i < times;i++){
            a += "-";
        }
        boolean hasLeft = false;
        boolean hasRight = false;
        int startLeft = index, startRight = lastIndex;
        for(int i = index + 1;i <= lastIndex - times;i++){
            if(s.substring(i, i+times).equals(a) && s.charAt(i - 1) != '-' && s.charAt(i + times) != '-'){
                if(startLeft == index){
                    startLeft = i;
                    hasLeft = true;
                }else{
                    startRight = i;
                    hasRight = true;
                }
            }
        }

        System.out.println("index is:======" + index + "   startLeft is:-----" + startLeft + "   str is:----" + s.substring(index, startLeft) + " lastIndex is:-=====" + lastIndex + "   startRight is:====" + startRight);
        int val = 0;

        if(hasLeft){
            val = Integer.parseInt(s.substring(index, startLeft));
        }else{
            val = Integer.parseInt(s.substring(index, lastIndex + 1));
        }
        TreeNode node = new TreeNode(val);
        int count = times + 1;
        if(hasLeft) {
            node.left = buildTree(s, startLeft + times, startRight < lastIndex ? startRight - 1 : startRight, count);
        }
        if(hasRight) {
            node.right = buildTree(s, startRight + times, lastIndex, count);
        }
        return node;
    }



    public TreeNode dfsBuildTreeNode(String S, int index, int lastHeight, int len){

        //System.out.println("String is :=====" + S);
        System.out.println();
        if(index >= len){
            return null;
        }
        int start = index + 1;
        while (start < S.length() && S.charAt(start) != '-'){
            start ++;
        }

        int end = start + 1;
        while (end < S.length() && S.charAt(end) == '-'){
            end++;
        }
        int height = end - start;
        System.out.println("height====" + height);
        int val = Integer.parseInt(S.substring(index, start));
        TreeNode node = new TreeNode(val);
        if(height > lastHeight){

            System.out.println("node is :=--" + node.val +  "===left-----");
            node.left = dfsBuildTreeNode(S, end, height, len);
        }else{
            System.out.println("node is :=--" + node.val +  "===right-----");
            node.right = dfsBuildTreeNode(S, end, height, len);
        }
        System.out.println("node is:======" + node);
        return node;

    }


    /**
     * 297. 二叉树的序列化与反序列化 hard
     * 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
     *
     * 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
     *
     * 示例:
     *
     * 你可以将以下二叉树：
     *
     *     1
     *    / \
     *   2   3
     *      / \
     *     4   5
     *
     * 序列化为 "[1,2,3,null,null,4,5]"
     * 提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
     *
     * 说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。
     *
     * 解题思路： 可以基于bfs、dfs求解
     * @param root
     * @return
     */
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {

        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res.toString();
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.peek();
            if(node != null){
                res.add(node.val);
                if(node.left != null){
                    queue.add(node.left);
                }else{
                    queue.add(null);
                }
                if(node.right != null){
                    queue.add(node.right);
                }else{
                    queue.add(null);
                }
            }else{
               res.add(null);
            }
            queue.poll();
        }

        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {

        String [] inputs = data.substring(1, data.length() - 1).split(",");
        if(inputs.length <= 0){
            return null;
        }
        if(inputs.length == 1){
            if(inputs[0].trim().equals("")){
                return null;
            }
        }
        TreeNode root = new TreeNode(Integer.parseInt(inputs[0]));
        Queue <TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode parent = null;
        for(int i = 1;i < inputs.length;i++){
            System.out.println("-----" + inputs[i]);
            parent = queue.peek();
            TreeNode node = null;
            if(!inputs[i].trim().equals("null")){
                Integer v = Integer.valueOf(inputs[i].trim());
                node = new TreeNode(v);
            }
            if(i%2 == 1){
                parent.left = node;
                if(node != null) {
                    queue.add(node);
                }
            }else{
                parent.right = node;
                if(node != null) {
                    queue.add(node);
                }
                queue.poll();
            }

        }
        return root;
    }


    /**
     * @author zlx
     * @desc 105. 从前序与中序遍历序列构造二叉树
     * 根据一棵树的前序遍历与中序遍历构造二叉树。
     *
     * 注意:
     * 你可以假设树中没有重复的元素。
     *
     * 例如，给出
     *
     * 前序遍历 preorder = [3,9,20,15,7]
     * 中序遍历 inorder = [9,3,15,20,7]
     * 返回如下的二叉树：
     *
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
     * @date  2020-05-26
     * @param preorder
     * @param  inorder
     * @return com.my.leetcode.TreeNode
     **/
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        if(preorder == null || inorder == null || (preorder.length != inorder.length)){
            return  null;
        }
        Map<Integer, Integer> inorderMap = new HashMap<>();
        for(int i = 0;i < inorder.length;i++){
            inorderMap.put(inorder[i], i);
        }
        return buildTree(preorder, inorder, inorderMap, 0, preorder.length - 1, 0, inorder.length - 1);
    }


    public TreeNode buildTree(int [] preorder, int [] inorder, Map<Integer, Integer> inorderMap, int preLeft, int preRight, int inLeft, int inRight){

        System.out.println("preLeft:    " + preLeft);
        System.out.println("preRight:   " + preRight);
        System.out.println("inleft:     " + inLeft);
        System.out.println("inright:    " + inRight);
        System.out.println("===================");
        if(preLeft > preRight || inLeft > inRight){
            System.out.println("return==========");
            return null;
        }
        int nodeVal = preorder[preLeft];
        TreeNode node = new TreeNode(nodeVal);

        int inIndex = inorderMap.get(nodeVal);
        node.left = buildTree(preorder, inorder, inorderMap, preLeft + 1, preLeft + inIndex - inLeft ,inLeft, inIndex - 1);
        node.right = buildTree(preorder, inorder, inorderMap, preLeft + inIndex - inLeft + 1, preRight,inIndex + 1, inRight);
        return node;
    }

    /**
     * @author zlx
     * @desc 98. 验证二叉搜索树 middle
     * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
     *
     * 假设一个二叉搜索树具有如下特征：
     *
     * 节点的左子树只包含小于当前节点的数。
     * 节点的右子树只包含大于当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树。
     * 示例 1:
     *
     * 输入:
     *     2
     *    / \
     *   1   3
     * 输出: true
     * 示例 2:
     *
     * 输入:
     *     5
     *    / \
     *   1   4
     *      / \
     *     3   6
     * 输出: false
     * 解释: 输入为: [5,1,4,null,null,3,6]。
     *      根节点的值为 5 ，但是其右子节点值为 4 。
     * @date  2020-05-08
     * @param root
     * @return boolean
     **/
    public boolean isValidBST(TreeNode root) {

        if(root == null){
            return true;
        }
        tmpRes = new ArrayList<>();
        dfsJudgeIsBST(root);
        System.out.println("res i s:=====" + tmpRes);
        for(int i = 1; i < tmpRes.size();i++){
            if(tmpRes.get(i) <= tmpRes.get(i - 1)){
                return false;
            }
        }
        return true;

    }


    public static List<Integer> tmpRes = new ArrayList<>();

    public void dfsJudgeIsBST(TreeNode node){
        if(node.left == null && node.right == null){
            tmpRes.add(node.val);
            return;
        }
        if(node.left != null){
            dfsJudgeIsBST(node.left);
        }
        tmpRes.add(node.val);
        if(node.right != null){
            dfsJudgeIsBST(node.right);
        }
    }

    /**
     * @author zlx
     * @desc 572. 另一个树的子树  easy
     * 给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
     *
     * 示例 1:
     * 给定的树 s:
     *
     *      3
     *     / \
     *    4   5
     *   / \
     *  1   2
     * 给定的树 t：
     *
     *    4
     *   / \
     *  1   2
     * 返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
     *
     * 示例 2:
     * 给定的树 s：
     *
     *      3
     *     / \
     *    4   5
     *   / \
     *  1   2
     *     /
     *    0
     * 给定的树 t：
     *
     *    4
     *   / \
     *  1   2
     * 返回 false。
     * @date 2020-05-07
     * @param s
     * @param t
     * @return boolean
     *
     * 解法一： 基于dfs进行求解，t可能是s的左子树，也可能是s的右子树，也可能相等
     **/
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if(s == null) {
            return false;
        }
        return isSameByDFS(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
    }

    /**
     * dfs判断子树是否相等
     * @param s
     * @param t
     * @return
     */
    public boolean isSameByDFS(TreeNode s, TreeNode t){

        if(s == null && t != null){
            return false;
        }

        if(s != null && t == null){
            return false;
        }
        if(s == null && t == null){
            return true;
        }
        if(s.val != t.val){
            return false;
        }
        return isSameByDFS(s.left, t.left) && isSameByDFS(s.right, t.right);

    }


    /**
     * 113. 路径总和 II
     * 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
     *
     * 说明: 叶子节点是指没有子节点的节点。
     *
     * 示例:
     * 给定如下二叉树，以及目标和 sum = 22，
     *
     *               5
     *              / \
     *             4   8
     *            /   / \
     *           11  13  4
     *          /  \    / \
     *         7    2  5   1
     * 返回:
     *
     * [
     *    [5,4,11,2],
     *    [5,8,4,5]
     * ]
     * @param root
     * @param sum
     * @return
     */
    List<List<Integer>> paths = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {

        paths = new LinkedList<>();
        dfsTree(root, new LinkedList<>(), sum, 0);
        System.out.println();
        return paths;
    }

    public void dfsTree(TreeNode node, List<Integer> path, int sum, int pathSum){

        if(node == null){
            return;
        }
        path.add(node.val);
        pathSum += node.val;
        if(node.left == null && node.right == null && pathSum == sum){
            //必须要加上这一段代码start，若不加，会paths会指向path，数量正确，内容为kong
            List<Integer> tmp = new LinkedList<>();
            for(Integer i: path) {
                tmp.add(i);
            }
            //必须要加上这一段代码end
            paths.add(tmp);
        }
        dfsTree(node.left, path, sum, pathSum);
        dfsTree(node.right, path, sum, pathSum);
        path.remove(path.size() - 1);
    }


    public void dfsTree(TreeNode node, List<Integer> path, List<List<Integer>> paths, int sum, int pathSum){
        if(node == null){
            return;
        }
        path.add(node.val);
        pathSum += node.val;
        if(node.left == null && node.right == null && pathSum == sum){
            System.out.println();
            System.out.println("path is:=====" + path);
            List<Integer> tmp = new LinkedList<>();
            for(Integer i: path){
                tmp.add(i);
            }
            System.out.println("path----------before add---------------" + paths);
            paths.add(tmp);
            System.out.println("path==================" + paths);
            System.out.println();
        }
        dfsTree(node.left, path, paths, sum, pathSum);
        dfsTree(node.right, path, paths, sum, pathSum);
        path.remove(path.size() - 1);
    }
    /**
     * medium
     * 129. 求根到叶子节点数字之和
     * 给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
     *
     * 例如，从根到叶子节点路径 1->2->3 代表数字 123。
     *
     * 计算从根到叶子节点生成的所有数字之和。
     *
     * 说明: 叶子节点是指没有子节点的节点。
     *
     * 示例 1:
     *
     * 输入: [1,2,3]
     *     1
     *    / \
     *   2   3
     * 输出: 25
     * 解释:
     * 从根到叶子节点路径 1->2 代表数字 12.
     * 从根到叶子节点路径 1->3 代表数字 13.
     * 因此，数字总和 = 12 + 13 = 25.
     * 示例 2:
     *
     * 输入: [4,9,0,5,1]
     *     4
     *    / \
     *   9   0
     *  / \
     * 5   1
     * 输出: 1026
     * 解释:
     * 从根到叶子节点路径 4->9->5 代表数字 495.
     * 从根到叶子节点路径 4->9->1 代表数字 491.
     * 从根到叶子节点路径 4->0 代表数字 40.
     * 因此，数字总和 = 495 + 491 + 40 = 1026.
     * @param root
     * @return
     */
    int sum = 0;
    public int sumNumbers(TreeNode root) {
        /*sum = 0;
        dfsTree(root, new LinkedList<>());
        return sum;
        */
        res = 0;
        dfsTree(root, 0);
        return res;
    }

    /**
     * 129. 求根到叶子节点数字之和 解法：基于深度优先遍历求解， 边求解边相加
     */

    public void dfsTree(TreeNode node, int sum){

        if(node == null){
            return ;
        }
        sum = sum * 10 + node.val;
        if(node.left == null && node.right == null){
            res += sum;
        }
        dfsTree(node.left, sum);
        dfsTree(node.right, sum);

    }

    /**
     * 129. 求根到叶子节点数字之和 解法：基于深度优先遍历求解，一条路径找完之后整体求和
     * 效率比 dfsTree(TreeNode node, int sum) 底
     * @param node
     * @param path
     */
    public void dfsTree(TreeNode node, List<Integer> path){

        if(node == null){
            return ;
        }
        path.add(node.val);
        if(node.left == null && node.right == null){
            String tem = "";
            for(Integer i : path){
                tem += i;
            }
            sum += Integer.parseInt(tem);
        }
        dfsTree(node.left, path);
        dfsTree(node.right, path);
        path.remove(path.size() - 1);
    }



    /**
     * easy
     * 257. 二叉树的所有路径
     * 给定一个二叉树，返回所有从根节点到叶子节点的路径。
     *
     * 说明: 叶子节点是指没有子节点的节点。
     *
     * 示例:
     *
     * 输入:
     *
     *    1
     *  /   \
     * 2     3
     *  \
     *   5
     *
     * 输出: ["1->2->5", "1->3"]
     *
     * 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
     * @param root
     * @return
     */
    public static List<String> binaryTreePaths(TreeNode root) {

        if(root == null){
            return new ArrayList<>();
        }

        List<String> res = new LinkedList<>();
        dfsBinaryTreePaths(new ArrayList<>(), root, res);
        return res;
    }



    public static void dfsBinaryTreePaths(List<String> path, TreeNode root, List<String> res){

        if(root == null){
            return;
        }
        path.add(String.valueOf(root.val));

        if(root.left == null && root.right == null){
            System.out.println(path.toString());
            String tmp = "";
            for(String p : path){
                tmp += p + "->";
            }
            res.add(tmp.substring(0, tmp.length() - 2));
        }
        dfsBinaryTreePaths(path, root.left, res);
        dfsBinaryTreePaths(path, root.right, res);
        path.remove(path.size() - 1);

    }


    /**
     * 337. 打家劫舍 III
     * 在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
     *
     * 计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
     *
     * 示例 1:
     *
     * 输入: [3,2,3,null,3,null,1]
     *
     *      3
     *     / \
     *    2   3
     *     \   \
     *      3   1
     *
     * 输出: 7
     * 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
     * 示例 2:
     *
     * 输入: [3,4,5,1,3,null,1]
     *
     *      3
     *     / \
     *    4   5
     *   / \   \
     *  1   3   1
     *
     * 输出: 9
     * 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
     *
     *
     * [4,1,null,2,null,3]    7
     *
     *
     * 解题思路：
     *  对当前节点来说，有2中状态：偷/不偷
     *  若当前节点偷，那么其孩子节点一定不能偷；
     *  若当前节点不偷， 只需要两个孩子节点的最大钱数（孩子节点可偷、可不偷）
     *
     *  因此：
     *  当前节点偷钱， 该节点最大偷钱数= 左孩子节点自己不偷时最大偷钱数+ 右孩子节点自己不偷时最大偷钱数 + 当前节点能偷的钱数；
     *
     *  当前节点不偷钱， 该节点最大偷钱数= 左孩子最大偷钱数+ 右孩子最大偷钱数；
     *
     *  root[1] 该根节点偷， root[0] 该节点不偷：
     *  root[1] =  root.left[0] + root.right[0] +root.val
     *  root[0] =  Math.max(root.left[0], root.left[1]) + Math.max(root.right[0], root.right[1]);
     *
     * @param root
     * @return
     */
    public static int rob(TreeNode root) {

        int [] res = robInternal(root);

        return Math.max(res[0], res[1]);
    }


    public static int [] robInternal(TreeNode node){

        if(node == null){
            return new int[2];
        }

        int [] res = new int[2];
        int [] left = robInternal(node.left);
        int [] right = robInternal(node.right);

        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        res[1] = left[0] + right[0] + node.val;

        System.out.println(node.val);
        System.out.println("left[0]=" + left[0]);
        System.out.println("left[1]=" + left[1]);
        System.out.println("right[0]=" + right[0]);
        System.out.println("right[1]=" + right[1]);
        System.out.println("res[1]====" + res[0]);
        System.out.println("res[1]====" + res[1]);
        return res;
    }




    /**
     * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
     *
     * 示例 :
     * 给定二叉树
     *
     *           1
     *          / \
     *         2   3
     *        / \
     *       4   5
     * 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
     *
     * 注意：两结点之间的路径长度是以它们之间边的数目表示。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/diameter-of-binary-tree
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     *
     * 解题思路： 树的直径长度= max{左子树最长路径， 右子树最长路径， 经过根节点的最长路径 }
     * 左、右子树最长路径，可以递归求解子问题， 经过根节点的最长路径=左子树深度+右子树深度
     * 因此：
     *           树的直径长度= max{左子树深度+右子树深度， 左子树最长路径， 右子树最长路径，}
     * @param root
     * @return
     */
    public int diameterOfBinaryTree(TreeNode root) {

        diameter = 0;
        traverse(root);
        return diameter;
    }


    public int diameter;

    public int traverse(TreeNode node){

        if(node == null){
            return 0;
        }

        int left = traverse(node.left);
        int right = traverse(node.right);

        diameter = Math.max(diameter, left + right);
        return Math.max(left, right) + 1;
    }








    /**
     * 589. N叉树的前序遍历
     * @param root
     * @return
     *acc
    public List<Integer> preorder(Node root) {

        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }

        preOrderNTree(root, res);
        return  res;
    }


    public void preOrderNTree(Node node, List<Integer> res){
        if(node == null)
            return;

        res.add(node.val);
        List<Node> children = node.children;
        for(Node child : children){
            preOrderNTree(child, res);
        }
    }

    /**
     * 145 后序遍历
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {

        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        postorderTraversal(root, res);
        return res;
    }


    public void postorderTraversal(TreeNode node, List<Integer> res){

        if(node == null)
            return;
        postorderTraversal(node.left, res);
        postorderTraversal(node.right, res);
        res.add(node.val);
    }


    /**
     * 基于Stack 的后序遍历(需要补充)
     * @param node
     * @return
     */
    public List<Integer> postorderTraversalByStack(TreeNode node) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(node != null || !stack.isEmpty()){
            if(node != null){
                stack.push(node);
                node = node.left;
            }else{

                node = stack.pop();
                node = node.right;
                res.add(node.val);
            }
        }
        return res;
    }


    /**
     * 144. 二叉树的前序遍历
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {

        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }

        preorderTraversal(root, res);
        return res;
    }


    /**
     * 基于递归方式实现前序遍历
     * @param node
     * @param res
     */
    public void preorderTraversal(TreeNode node, List<Integer> res){

        if(node == null)
            return;
        res.add(node.val);
        preorderTraversal(node.left, res);
        preorderTraversal(node.right, res);

    }


    /**
     * 基于递归方式实现前序遍历
     * @param node
     * @return
     */
    public List<Integer> preOrderATraversalByStack(TreeNode node){

        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(node != null || !stack.isEmpty()){
          if(node != null){
              res.add(node.val);
              stack.push(node);
              node = node.left;
          }else{
              node = stack.pop();
              node = node.right;
          }
        }
        return res;

    }


    /**
     * 94. 二叉树的中序遍历
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {

        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        inorderTraversal(root, res);
        return res;
    }

    /**
     * 基于递归方式实现 中序遍历
     * @param node
     * @param res
     */
    public void inorderTraversal(TreeNode node, List<Integer> res){

        if(node == null){
            return;
        }
        inorderTraversal(node.left, res);
        res.add(node.val);
        inorderTraversal(node.right, res);

    }

    /**
     * 基于Stack 实现树的中序遍历， 时间、空间都比递归慢
     * @param node
     * @return
     */
    public List<Integer> inorderTraversalByStack(TreeNode node){

        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(node != null || !stack.isEmpty()){
            if(node != null){
                stack.push(node);
                node = node.left;
            }else{
                node = stack.pop();
                res.add(node.val);
                node = node.right;
            }

        }
        return res;
    }



    /**
     * 103
     * @param root
     * @return
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

        List<List<Integer>> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        int direction = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                if (queue.peek().left != null) {
                    queue.add(queue.peek().left);
                }

                if (queue.peek().right != null) {
                    queue.add(queue.peek().right);
                }
                level.add(queue.poll().val);
            }
            List<Integer> tmp = new LinkedList<>();
            if(direction % 2 == 1){
                for(int j = level.size() - 1; j>= 0;j--){
                    tmp.add(level.get(j));
                }
                res.add(tmp);
            }else
                res.add(level);
            direction++;

        }
        return res;
    }

    /**
     * 102. 二叉树的层次遍历
     * 给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
     * <p>
     * 例如:
     * 给定二叉树: [3,9,20,null,null,15,7],
     *
     * @param root 解题思路：借助Queue， 每层数据放入到队列中，进行便利
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                if (queue.peek().left != null) {
                    queue.add(queue.peek().left);
                }

                if (queue.peek().right != null) {
                    queue.add(queue.peek().right);
                }
                level.add(queue.poll().val);
            }
            res.add(level);
        }

        return res;
    }


    /**
     * 104. 二叉树的最大深度
     * 给定一个二叉树，找出其最大深度。
     * <p>
     * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
     * <p>
     * 说明: 叶子节点是指没有子节点的节点。
     * <p>
     * 示例：
     * 给定二叉树 [3,9,20,null,null,15,7]，
     * <p>
     * 返回 3
     *
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {

        if (root == null)
            return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    /**
     * 111. Minimum Depth of Binary Tree
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = minDepth(root.left);
        int right = minDepth(root.right);

        return (left == 0 || right == 0) ? (right + left + 1) : Math.min(left, right) + 1;
    }

}
